// 被围绕的区域

package Leetcode;

public class Solution130 {
    public void solve(char[][] board) {
        int m = board.length;
        int n = board[0].length;

        if (m == 0 || n == 0)
            return;

        for (int i = 0; i < n; i++) {
            dfs(board, 0, i);
            dfs(board, m - 1,  i);
        }

        for (int i = 0; i < m; i++) {
            dfs(board, i, 0);
            dfs(board, i, n - 1);
        }

        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'A')
                    board[i][j] = 'O';
                // 这里的else不能省略，否则会变成全为`X`
                else if (board[i][j] == 'O')
                    board[i][j] = 'X';
            }
    }

    public void dfs(char[][] board, int x, int y) {
        int m = board.length;
        int n = board[0].length;                 //这里不能写board[x][y] == 'X'，当矩阵全为`O`时会执行出错。
        if (x < 0 || x >= m || y < 0 || y >= n || board[x][y] != 'O')
            return;
        board[x][y] = 'A';
        dfs(board, x - 1, y);
        dfs(board, x + 1, y);
        dfs(board, x, y - 1);
        dfs(board, x, y + 1);
    }
}
